|
In computing, the producer–consumer problem (also known as the bounded-buffer problem) is a classic example of a multi-process synchronization problem. The problem describes two processes, the producer and the consumer, who share a common, fixed-size buffer used as a queue. The producer's job is to generate a piece of data, put it into the buffer and start again. At the same time, the consumer is consuming the data (i.e., removing it from the buffer) one piece at a time. The problem is to make sure that the producer won't try to add data into the buffer if it's full and that the consumer won't try to remove data from an empty buffer. The solution for the producer is to either go to sleep or discard data if the buffer is full. The next time the consumer removes an item from the buffer, it notifies the producer, who starts to fill the buffer again. In the same way, the consumer can go to sleep if it finds the buffer to be empty. The next time the producer puts data into the buffer, it wakes up the sleeping consumer. The solution can be reached by means of inter-process communication, typically using semaphores. An inadequate solution could result in a deadlock where both processes are waiting to be awakened. The problem can also be generalized to have multiple producers and consumers. == Inadequate implementation == To solve the problem, a less experienced programmer might come up with a solution shown below. In the solution two library routines are used, sleep and wakeup. When sleep is called, the caller is blocked until another process wakes it up by using the wakeup routine. The global variable itemCount holds the number of items in the buffer.int itemCount = 0; procedure producer() } } procedure consumer() consumeItem(item); } } The problem with this solution is that it contains a race condition that can lead to a deadlock. Consider the following scenario: # The consumer has just read the variable itemCount, noticed it's zero and is just about to move inside the if block.# Just before calling sleep, the consumer is interrupted and the producer is resumed. # The producer creates an item, puts it into the buffer, and increases itemCount.# Because the buffer was empty prior to the last addition, the producer tries to wake up the consumer. # Unfortunately the consumer wasn't yet sleeping, and the wakeup call is lost. When the consumer resumes, it goes to sleep and will never be awakened again. This is because the consumer is only awakened by the producer when itemCount is equal to 1.# The producer will loop until the buffer is full, after which it will also go to sleep. Since both processes will sleep forever, we have run into a deadlock. This solution therefore is unsatisfactory. An alternative analysis is that if the programming language does not define the semantics of concurrent accesses to shared variables (in this case itemCount) without use of synchronization, then the solution is unsatisfactory for that reason, without needing to explicitly demonstrate a race condition.抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Producer–consumer problem」の詳細全文を読む スポンサード リンク
|